/**
 * 给一个'UDLR'的字符串，表示在二维平面游走
 * 再给定一个k，表示要从字符串中删除长度为k的子串
 * 问删除子串后，最终不同的终点可能有多少个
 * 
 * 不删的话，终点是唯一的，因此有多少个本质不同的删除方法就有多少个不同的终点
 * 终点最终只由LR之差与UD之差决定
 * 做一个哈希或者set，记录即可
 */
struct _t{
    array<int, 2> a;
    _t():a{0,0}{}
    _t(int x, int y):a{x, y}{}
    bool operator < (const _t & right) const {
        for(int i=0;i<2;++i){
            if(a[i] != right.a[i]) return a[i] < right.a[i];
        }
        return false;
    }
};

class Solution {
public:
    int distinctPoints(string s, int k) {
        int cnt[256] = {0};
        set<_t> Set;

        for(int i=0;i<k;++i){
            cnt[s[i]] += 1;
        }
        Set.insert(_t{cnt['D'] - cnt['U'], cnt['L'] - cnt['R']});

        int n = s.length();
        for(int i=k;i<n;++i){
            cnt[s[i - k]] -= 1;
            cnt[s[i]] += 1;
            Set.insert(_t{cnt['D'] - cnt['U'], cnt['L'] - cnt['R']});
        }

        return Set.size();
    }
};